package main

import (
	"fmt"
	"strings"
)

type SortedSinglyLinkedList struct {
	head *Node
}

func (list *SortedSinglyLinkedList) Add(
	e interface{},
	comparator func(e1 interface{}, e2 interface{}) int) {

	node := &Node{e, nil}

	tmp := list.head

	for {
		if tmp.next == nil || comparator(tmp.next.e, e) > 0 {
			break
		}
		tmp = tmp.next
	}
	node.next = tmp.next
	tmp.next = node
}

func (list *SortedSinglyLinkedList) remove(
	e interface{},
	comparator func(e1 interface{}, e2 interface{}) int) (r interface{}) {

	tmp := list.head

	for {
		if tmp.next == nil {
			return nil
		}
		if comparator(tmp.next.e, e) == 0 {
			break
		}
		tmp = tmp.next
	}

	r = tmp.next.e
	tmp.next = tmp.next.next

	return
}

func (list *SortedSinglyLinkedList) Print() {
	next := list.head.next
	s := "["
	for {
		if next == nil {
			break
		}
		s += fmt.Sprintf("%v, ", next.e)
		next = next.next
	}
	fmt.Println(strings.TrimRight(strings.TrimSpace(s), ",") + "]")
}

func (list *SortedSinglyLinkedList) Peek() (e interface{}) {
	next := list.head.next
	if next == nil {
		return nil
	}
	return next.e
}

func (list *SortedSinglyLinkedList) Poll() (e interface{}) {
	next := list.head.next
	if next == nil {
		return nil
	}
	list.head.next = next.next
	next.next = nil
	return next.e
}

type Node struct {
	e    interface{}
	next *Node
}

type Student struct {
	id       int
	name     string
	nickname string
}

func (student *Student) String() string {
	return fmt.Sprintf("{id=%d, name=%s, nickname=%s}", student.id, student.name, student.nickname)
}

func main() {

	list := SortedSinglyLinkedList{&Node{}}

	s2 := &Student{2, "卢俊义", "玉麒麟"}
	s1 := &Student{1, "宋江", "及时雨"}
	s14x := &Student{14, "武松x", "行者x"}
	s3 := &Student{3, "吴用", "智多星"}
	s14 := &Student{14, "武松", "行者"}

	var f = func(e1 interface{}, e2 interface{}) int {
		return e1.(*Student).id - e2.(*Student).id
	}

	// 追加
	list.Add(s3, f)
	list.Add(s14, f)
	list.Add(s2, f)
	list.Add(s14x, f)
	list.Add(s1, f)

	// 遍历打印
	list.Print()

	// 获取第一个元素
	e := list.Peek()
	fmt.Printf("第一个元素是: %v\n", e)

	// 获取元素
	for {
		e1 := list.Poll()
		if e1 == nil {
			break
		}
		stu := e1.(*Student)
		fmt.Printf("%d %s %s\n", stu.id, stu.name, stu.nickname)
	}

	// 移除
	r := list.remove(&Student{id: 16}, f)
	fmt.Printf("移除的元素是: %v\n", r)
	r = list.remove(&Student{id: 14}, f)
	fmt.Printf("移除的元素是: %v\n", r)
	r = list.remove(&Student{id: 14}, f)
	fmt.Printf("移除的元素是: %v\n", r)
	r = list.remove(&Student{id: 14}, f)
	fmt.Printf("移除的元素是: %v\n", r)
	r = list.remove(&Student{id: 3}, f)
	fmt.Printf("移除的元素是: %v\n", r)
	r = list.remove(&Student{id: 1}, f)
	fmt.Printf("移除的元素是: %v\n", r)
	r = list.remove(&Student{id: 2}, f)
	fmt.Printf("移除的元素是: %v\n", r)
	r = list.remove(&Student{id: 2}, f)
	fmt.Printf("移除的元素是: %v\n", r)

	// 遍历打印
	list.Print()
}
